package middle;

/**
 * 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class MaximumLengthOfRepeatedSubarray {
    /**
     * DP
     * 这种最让人联想到DP
     * 1.定义含义：dp[i][j] 表示当nums1数组长度为i时，nums2数组长度为j时的公共子数组的长度。
     * 2.找出状态转移方程：
     * 对于当前nums1[i] == nums2[j]  dp[i][j] = dp[i-1][j-1] + 1
     * 对于当前nums1[i] != nums2[j] dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j])
     *
     * 3.初始化数组
     * num[0~n][0] = 0;
     * nums[0][0~m] = 0;
     * */
    class Solution {
        public int findLength(int[] nums1, int[] nums2) {
            int[][] dp = new int[nums1.length+1][nums2.length+1];
            int res = 0;
            for (int i = 1; i < nums1.length; i++) {
                for (int j = 1; j < nums2.length; j++) {
                    if(nums1[i-1] == nums2[j-1]){
                        dp[i][j] = dp[i-1][j-1] + 1;
                    }
                    res = Math.max(dp[i][j], res);

                }
            }
            return res;
        }
    }
}
